package class01

import (
	"traning/algorithm/utility"
)

/*
	给定一个二维数组 matrix，可以从任何位置出发，每一步可以向上，下，
	左，右四个方向。返回最大递增链的长度。

	例子：
		matrix =
		5 4 3
		3 1 2
		2 1 3
	从最中心的位置1出发，是可以走出1 2 3 4 5的链的，而且这是最长的递增链。所以
	返回长度5
*/
func MaxPath(matrix [][]int) int {
	var ans int
	for i:=0; i<len(matrix); i++ {
		for j:=0; j<len(matrix[i]); j++ {
			ans = utility.Max(ans, MaxPathProcess(matrix, i, j))
		}
	}
	return ans
}

func MaxPathProcess(matrix [][]int, i, j int) int {
	if i < 0 || i > len(matrix)-1 || j < 0 || j > len(matrix[0]) - 1 {
		// 越界直接返回-1
		return -1
	}
	var up, left, right, down int
	if i-1 >= 0 && matrix[i-1][j] > matrix[i][j] {
		up = MaxPathProcess(matrix, i-1, j)
	}
	if j-1 >= 0 && matrix[i][j-1] > matrix[i][j] {
		left = MaxPathProcess(matrix, i, j-1)
	}
	if j+1 <= len(matrix[0]) - 1 && matrix[i][j+1] > matrix[i][j] {
		right = MaxPathProcess(matrix, i, j+1)
	}
	if i+1 <= len(matrix) - 1  && matrix[i+1][j] > matrix[i][j] {
		down = MaxPathProcess(matrix, i+1, j)
	}
	return utility.Max(utility.Max(up, left), utility.Max(right, down)) + 1
}

func MaxPath1(matrix [][]int) int {
	var ans int
	cache := make([][]int, len(matrix))
	for i:=0; i<len(cache); i++ {
		cache[i] = make([]int, len(matrix[i]))
	}

	for i:=0; i<len(matrix); i++ {
		for j:=0; j<len(matrix[i]); j++ {
			ans = utility.Max(ans, MaxPathProcess1(matrix, i, j, cache))
		}
	}
	return ans
}

func MaxPathProcess1(matrix [][]int, i, j int, cache [][]int) int {
	if i < 0 || i > len(matrix)-1 || j < 0 || j > len(matrix[0]) - 1 {
		// 越界直接返回-1
		return -1
	}
	if cache[i][j] != 0 {
		return cache[i][j]
	}
	var up, left, right, down int
	if i-1 >= 0 && matrix[i-1][j] > matrix[i][j] {
		up = MaxPathProcess(matrix, i-1, j)
	}
	if j-1 >= 0 && matrix[i][j-1] > matrix[i][j] {
		left = MaxPathProcess(matrix, i, j-1)
	}
	if j+1 <= len(matrix[0]) - 1 && matrix[i][j+1] > matrix[i][j] {
		right = MaxPathProcess(matrix, i, j+1)
	}
	if i+1 <= len(matrix) - 1  && matrix[i+1][j] > matrix[i][j] {
		down = MaxPathProcess(matrix, i+1, j)
	}
	cache[i][j] = utility.Max(utility.Max(up, left), utility.Max(right, down)) + 1
	return cache[i][j]
}